/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package search;

import agents.AutomatonAgent;
import env.Action;
import env.Enviroment;
import env.Tile;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

/**
 *
 * @author user
 */
public class HeuristicBFS extends Heuristic {

    private HashMap<Tile, HashMap<Tile, Integer>> SP_distances = new HashMap<Tile, HashMap<Tile, Integer>>();
    private HashMap<Tile, HashMap<Tile, Integer>> sentry_LOS_left = new HashMap<Tile, HashMap<Tile, Integer>>();
    private HashMap<Tile, HashMap<Tile, Integer>> sentry_LOS_right = new HashMap<Tile, HashMap<Tile, Integer>>();

    @Override
    int dist_death() {
        return dist_from_sentry(state.sentryState.getTile(), state.myState.getTile(), AutomatonAgent.nextMove(state.sentryState));
    }

    @Override
    int dist_farthest_flag() {
        int d = 0;
        Tile current = state.getTile();
        for (Tile flag : state.getFlags()) {
            int temp = dist_to(flag, current);
            if (temp > d) {
                d = temp;
            }
        }
        return d;
    }

    /**********************************************************************
     **********************************************************************
     * 
     *        hash-map building
     * 
     ***********************************************************************
     ***********************************************************************
     */
    private int dist_to(Tile flag, Tile other) {
        HashMap<Tile, Integer> dist = SP_distances.get(flag);
        if (dist == null) {
            dist = new HashMap<Tile, Integer>();
            SP_distances.put(flag, dist);
            dist.put(flag, 0);
            BFS_extend_from_source(dist, flag, "dist");
        }
        Integer ans = dist.get(other);
        if (ans == null) {
            System.err.println("dist_to table of " + flag + " doesn't contain " + other + " which means it's unreachable!");
            return Integer.MAX_VALUE;
        }
        return ans.intValue();
    }


    /**
     * 
     * @param sentry_tile       where the sentry is
     * @param other             where the agent is
     * @param sentry_direction  which direction is the sentry heading
     * @return the distance, if there was no ice
     */
    private int dist_from_sentry(Tile sentry_tile, Tile other, Action sentry_direction) {
        HashMap<Tile, Integer> map = (sentry_direction == Action.left ? sentry_LOS_left.get(sentry_tile) : sentry_LOS_right.get(sentry_tile));
        if (map == null) {
            map = new HashMap<Tile, Integer>();
            if (sentry_direction == Action.left) {
                sentry_LOS_left.put(sentry_tile, map);
            } else {
                sentry_LOS_right.put(sentry_tile, map);
            }
            Tile t = sentry_tile;
            int i = 0;
            while (!t.isWall()) {
                fill_col_with_d(map, t, i++);
                t = t.getNeighbor(sentry_direction);
            }
            sentry_direction = sentry_direction.opposite();
            t = sentry_tile.getNeighbor(sentry_direction);
            while (!t.isWall()) {
                fill_col_with_d(map, t, i++);
                t = t.getNeighbor(sentry_direction);
            }
            BFS_extend_from_source(map, sentry_tile, "dist_from_sentry");
        }
        Integer ans = map.get(other);
        if (ans == null) {
            //System.err.println("dist_from_sentry at " + sentry_tile + " doesn't contain " + other + " which means it's unreachable!");
            return Integer.MAX_VALUE;
        }
        return ans.intValue();

    }
    /**
     * just a helper for dist_from_sentry
     * @param t
     * @param map
     * @param d
     * @param dir
     */
    private void run_on_col_with_val(Tile t, HashMap<Tile, Integer> map, Integer d, Action dir) {
        for (Tile q = t.getNeighbor(dir); !q.isWall(); q = q.getNeighbor(Action.down)) {
            map.put(q, d);
        //q.label.setToolTipText("run_on_col_with_val on col, dist from " + row + "," + col + " = " + d);
        }
    }

    /**
     * just a helper for dist_from_sentry
     * @param map
     * @param t
     * @param d
     */
    private void fill_col_with_d(HashMap<Tile, Integer> map, Tile t, Integer d) {
        map.put(t, 0);
        run_on_col_with_val(t, map, d, Action.down);
        run_on_col_with_val(t, map, d, Action.up);
    //t.label.setToolTipText("fill_col_with_d on row, dist from " + row + "," + col + " = " + d);
    }
    
    /**
     * the BFS...
     * @param map the map(Tile -> int)  to improve upon
     * @param source the source, usually map(source)=0 but not neccesary
     * @param str   just for debug
     */
    private static void BFS_extend_from_source(HashMap<Tile, Integer> map, Tile source, String str) {
        LinkedList<Tile> queue = new LinkedList<Tile>();
        HashSet<Tile> closed = new HashSet<Tile>();
        queue.add(source);
        closed.add(source);
        while (!queue.isEmpty()) {
            Tile t = queue.removeFirst();
            //System.out.println("expanding "+t);
            for (Action dir : Action.values()) {
                final Tile n = t.getNeighbor(dir);
                final int dist = map.get(t) + 1;
                if (!n.isWall() && !closed.contains(n)) {
                    if (!map.containsKey(n) || map.get(n) > dist) {
                        map.put(n, dist);
                    }
                    closed.add(n);
                    queue.addLast(n);
//                    if(str!=null)
//                        n.label.setToolTipText("BFS " +str + " from " + row + "," + col + " = " + dist);
                }
            }
        }
    //System.out.println(" BFS for "+str+" is done! d.size=" + map.size());
    }
}
